/*************************************************************************
 *  Compilation:  javac ThreeSumFast.java
 *  Execution:    java ThreeSumFast input.txt
 *  Data files:   http://algs4.cs.princeton.edu/14analysis/1Kints.txt
 *                http://algs4.cs.princeton.edu/14analysis/2Kints.txt
 *                http://algs4.cs.princeton.edu/14analysis/4Kints.txt
 *                http://algs4.cs.princeton.edu/14analysis/8Kints.txt
 *                http://algs4.cs.princeton.edu/14analysis/16Kints.txt
 *                http://algs4.cs.princeton.edu/14analysis/32Kints.txt
 *                http://algs4.cs.princeton.edu/14analysis/1Mints.txt
 *
 *  A program with N^2 log N running time. Read in N integers
 *  and counts the number of triples that sum to exactly 0.
 *
 *  Limitations
 *  -----------
 *     - we ignore integer overflow
 *     - doesn't handle case when input has duplicates
 *
 *
 *  % java ThreeSumFast 1Kints.txt
 *  70
 *  
 *  % java ThreeSumFast 2Kints.txt
 *  528
 *                
 *  % java ThreeSumFast 4Kints.txt
 *  4039
 * 
 *  % java ThreeSumFast 8Kints.txt
 *  32074
 *
 *  % java ThreeSumFast 16Kints.txt
 *  255181
 *
 *  % java ThreeSumFast 32Kints.txt
 *  2052358
 *
 *************************************************************************/

import java.util.Arrays;

public class ThreeSumFast {

	// print distinct triples (i, j, k) such that a[i] + a[j] + a[k] = 0
	public static void printAll(int[] a) {
		int N = a.length;
		Arrays.sort(a);
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				for (int k = j + 1; k < N; k++) {
					int l = Arrays.binarySearch(a, -(a[i] + a[j] + a[k]));
					if (l > k)
						StdOut.println(a[i] + " " + a[j] + " " + a[k] + " "
								+ a[l]);
				}

			}
		}
	}

	// return number of distinct triples (i, j, k) such that a[i] + a[j] + a[k]
	// = 0
	public static int count(int[] a) {
		int N = a.length;
		Arrays.sort(a);
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				for (int k = j + 1; k < N; k++) {
					int l = Arrays.binarySearch(a, -(a[i] + a[j] + a[k]));
					if (l > k)
						cnt++;
				}
			}
		}
		return cnt;
	}

	public static int count(Double[] a) {
		int N = a.length;
		Arrays.sort(a);
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				for (int k = j + 1; k < N; k++) {
					int l = Arrays.binarySearch(a, -(a[i] + a[j] + a[k]));
					if (l > k)
						cnt++;
				}
			}
		}
		return cnt;
	}

	public static int countBrute(Double[] a) {
		int N = a.length;
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				for (int k = j + 1; k < N; k++) {
					for (int l = k + 1; l < N; l++) {
						if (a[i] + a[j] + a[k] + a[l] == 0)
							cnt++;
					}
				}
			}
		}
		return cnt;
	}

	public static void main(String[] args) {
		QuickArray<Double> a = new QuickArray();
		In in = new In(args[0]);
		while (in.hasNextLine()) {
			String tmpS = in.readLine();
			if (tmpS.contains(",")) {
				a.add(Double.parseDouble(tmpS.substring(tmpS.indexOf(",") + 1)));
			} else {
				a.add(Double.parseDouble(tmpS));
			}
		}
		Double[] array = a.getDoubleArray();
		double avg = 0;
		int cnt = 0;
		for (int i = 0; i < 1; i++) {
			Stopwatch sw = new Stopwatch();
			cnt = count(array);
			avg += sw.elapsedTime();
		}
		System.out.println("Time: " + avg);
		StdOut.println(cnt + " (N:" + array.length + ")");
		int bcnt = countBrute(array);
		StdOut.println(bcnt + " Brute force");
	}
}